Interval List Intersections

Medium

Question

Given two non-overlappinglists of intervals, return a new list of intervals which are intersections of the two lists.

The lists given to you are already sorted by their the intervals' first value.

The intervals' first value is always less than or equal to its second value.

Input: list_a = [[0, 3], [4, 5], [6, 7]], list_b = [[1, 2], [7, 7]]

Output: [[1, 2], [7, 7]]

Intervals [0, 3] and [1, 2] intersect at [1, 2] and intervals [6, 7] and [7, 7] intersect at [7, 7].

Input: list_a = [[3, 3], [4, 6], [7, 7]], list_b = [[1, 5]]

Output: [[3, 3], [4, 5]]

None of the intervals intersect since the second list is empty.

Input: list_a = [[0, 3], [4, 5], [6, 7]], list_b = []

Output: []

None of the intervals intersect since the second list is empty.

What are some questions you'd ask an interviewer?

What is the list of interval intersections of these two lists? list_a = [[1, 4], [9, 15]], list_b = [[2, 6], [8, 10], [13, 14]]

[]

[[1, 6], [8, 15]]

[[2, 4], [9, 10], [13, 14]]

[[1, 1], [5, 6], [8, 8], [11, 12], [15, 15]]

Take a moment to understand the problem and think of your approach before you start coding.

Bookmark

Reset